#ifndef __EXPR_PARSER__
#define __EXPR_PARSER__

#include <cassert>

#include <istream>
#include <memory>
#include <stdexcept>
#include <typeinfo>

#include <tr1/memory>

namespace std
{
	using std::tr1::shared_ptr;
}

#define nullptr 0

namespace tdop
{
	class SyntaxError : public std::runtime_error
	{
	public:
		SyntaxError(char const* what) : std::runtime_error(what)
		{
		}
	};
	
	template <typename T> class Token
	{
	public:
		virtual ~Token()
		{
		}

		unsigned int lbp() const
		{
			return lbp_;
		}

		typedef std::shared_ptr< Token<T> > Ptr;

	protected:
		explicit Token(unsigned int lbp) : lbp_(lbp)
		{
		}

	private:
		unsigned int lbp_;
	};

	template <typename T> class EndOfFileToken : public Token<T>
	{
	public:
		EndOfFileToken() : Token<T>(0) {}
	};

	template <typename T> class Parser
	{
	public:
		T parse()
		{
			token_ = get_token_();

			return expression(0);
		}

	protected:
		T expression(unsigned int rbp)
		{
			assert(token_);

			typename Token<T>::Ptr t = token_;

			token_ = get_token_();

			T left = nud(*t);

			if (typeid(*token_) == typeid(EndOfFileToken<T>))
				return left;

			while (rbp < token_->lbp())
			{
				t = token_;
			
				token_ = get_token_();

				left = led(left, *t);
			}

			return left;
		}

		void match(std::type_info const& token_type)
		{
			if (!token_ || typeid(*token_) != token_type)
				throw SyntaxError("cannot match token");

			token_ = get_token_();
		}

	private:
		virtual typename Token<T>::Ptr get_token() = 0;
		virtual T nud(Token<T> const& token) = 0;
		virtual T led(T left, Token<T> const& token) = 0;

	private:
		typename Token<T>::Ptr get_token_()
		{
			typename Token<T>::Ptr token = get_token();

			if (!token)
				token.reset(new EndOfFileToken<T>);
						
			return token;
		}

	private:
		typename Token<T>::Ptr token_;
	};
}

#endif // __EXPR_PARSER__
